//计数排序
//要求输入的数据具有明确的范围

//步骤：1.先找出数组中最大的元素max，max+1为计数数组count的长度
//2.利用count的下标对应上arr的元素，count[i]记录元素i在arr中的出现次数
//3.遍历count数组，数组下标相当于对应上arr中元素排序后的顺序，只是没有算上出现次数，那么就访问count[i]，并且将出现次数不为0的元素依次放入arr，直到出现次数减为0为止
//index记录下一个应当放入元素的位置

import java.util.Arrays;

public class countingSort {
    public static void main(String[] args) {
        int[] arr = new int[] {3,2,2,8,6,6,1,9};
        int max = getMaxValue(arr);
        int[] res = sort(arr,max);
        System.out.println(Arrays.toString(res));
    }

    public static int[] sort(int[] arr, int max){
        int len = max + 1;
        int[] count = new int[len];
        for(int i = 0 ; i < arr.length ; i++){
            count[arr[i]]++;
        }
        int index = 0;
        for(int j = 0 ; j < len ; j++){
            while(count[j] > 0){
                arr[index++] = j;
                count[j]--;
            }
        }
        return arr;
    }

    public static int getMaxValue(int[] arr){
        int max = Integer.MIN_VALUE;
        for(int i = 0 ; i < arr.length ; i++){
            if(arr[i] > max){
                max = arr[i];
            }
        }
        return max;
    }
}
